package com.kevin.Code.String;

/**
 * @author Vinlee Xiao
 * @Classname LongestPalindromicSubstring
 * @Description Leetcode 5. 最长回文子串 中等难度 二刷 i/2,i/2+i%2
 * @Date 2022/3/8 15:03
 * @Version 1.0
 */
public class LongestPalindromicSubstring {

    /**
     * 中心扩散法
     *
     * @param s 字符子串
     * @return String
     */
    public String longestPalindrome(String s) {

        int length = s.length();
        int maxLength = 0;
        String result = "";
        //用来回文子串的长度
        int count = 0;
        if (length == 1) {
            return s;
        }

        for (int i = 0; i < 2 * length - 1; i++) {
            //本题的精髓 如果i为偶数比较的就是同一个 否则比较的是相邻的两个数 所以次数不能大于2*length-1
            int left = i / 2;
            int right = i / 2 + i % 2;

            while (left >= 0 && right < length && s.charAt(left) == s.charAt(right)) {
                if (left != right) {
                    count += 2;
                } else {
                    count++;
                }
                if (count > maxLength) {
                    result = s.substring(left, right + 1);
                    maxLength = count;
                }
                left--;
                right++;

            }


            count = 0;
        }


        return result;
    }

    public static void main(String[] args) {
        LongestPalindromicSubstring l = new LongestPalindromicSubstring();
        String s = l.longestPalindrome("babad");
        System.out.println(s);
    }
}
